package com.example.datastruct;

import java.util.Arrays;
import java.util.List;
import java.util.concurrent.*;
import java.util.concurrent.locks.ReentrantLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

public class Test {

        public synchronized String GetMapping(){
        return "a";
    }


    public static void main(String[] args) throws InterruptedException {

        List<Integer> integers = Arrays.asList(6664, 63,1,77,33333,555,22);

        Integer[] arrayList = {};
        final Integer[] integers1 = integers.toArray(arrayList);
//        insertSort(integers1);

        int[] array = {5, 9, 1, 9, 5, 3, 7, 6, 1};
        quickSortExt(array,0,array.length - 1);

        for(Integer integer: array) {
            System.out.println(integer);
        }



        ReentrantReadWriteLock readWriteLock = new ReentrantReadWriteLock();

        CountDownLatch countDownLatch = new CountDownLatch(4);

        countDownLatch.countDown();

        ReentrantLock lock = new ReentrantLock(true);

        lock.lock();

        lock.unlock();

        int oldCapacity = 4;

        synchronized (Test.class){

        }

        final ExecutorService executorService = Executors.newFixedThreadPool(4);

        executorService.execute(()->{



        });

        lock.wait();

        ArrayBlockingQueue arrayBlockingQueue = new ArrayBlockingQueue(16);

        LinkedBlockingQueue linkedBlockingQueue = new LinkedBlockingQueue();




    }

    /**
     * 二分查找
     * 返回查找数组的位置
     * @param array
     * @param value
     * @return
     */
    public static int binarySearch(int[] array,int value) {

        int len = array.length - 1;
        int mid = 0;
        int start = 0;

        while (start <= len) {

            mid = (start + len) / 2;

            if(array[mid]== value) {
                return mid +1;
            }else if(array[mid] < value) {
                start = mid;
            }else{
                len = mid -1;
            }
        }


        return  -1;
    }

    /**
     * 冒泡排序
     * @param a
     * @param n
     */
    public static void bubbleSort1(int [] a, int n){
        int i, j;

        for(i=0; i<n; i++){//表示 n 次排序过程。
            for(j=1; j<n-i; j++){
                if(a[j-1] > a[j]){//前面的数字大于后面的数字就交换
                    //交换 a[j-1]和 a[j]
                    int temp;
                    temp = a[j-1];
                    a[j-1] = a[j];
                    a[j]=temp;
                }
            }
        }
    }

    /**
     * 冒泡排序
     * @param array
     */
    public static void bubblesort(Integer[] array) {


        for(int i = 0;i<=array.length; i++){

            for(int j= 1; j <= array.length-1;j++) {

                if(array[j-1] > array[j]) {
                    int temp = array[j];
                    array[j] = array[j-1];
                    array[j-1] = temp;
                }
            }
        }
    }

    /**
     * 插入排序
     * @param array
     */
    public static void insertSort(Integer[] array) {

        for (int i =1;i<array.length;i++) {

            for(int j =i;j > 0;j--) {

                if(array[j-1] > array[j]) {
                    int temp = array[j];
                    array[j] = array[j-1];
                    array[j-1] = temp;
                }
            }
        }

    }

    /**
     * 快速排序
     * 原理 从基准值开始遍历
     * 从后往前比较
     * 从前往后比较
     * 反复循环
     */
    /**
     * 递归排序
     * @param src
     * @param begin
     * @param end
     */
    public static void quickSort(int[] src, int begin, int end) {
        if (begin < end) {
            int key = src[begin];
            int i = begin;
            int j = end;
            while (i < j) {
                while (i < j && src[j] > key) {
                    j--;
                }
                if (i < j) {
                    src[i] = src[j];
                    i++;
                }
                while (i < j && src[i] < key) {
                    i++;
                }
                if (i < j) {
                    src[j] = src[i];
                    j--;
                }
            }
            src[i] = key;
            quickSort(src, begin, i - 1);
            quickSort(src, i + 1, end);
        }
    }


    /**
     *
     * @param src
     * @param begin
     * @param end
     */
    public static void quickSortExt(int[] src, int begin, int end) {

        if(begin < end) {

            int orgin = src[begin]; //取基准值
            int i = begin;
            int j = end;

            while(i < j) {
                while(i < j && src[j] > orgin) {
                    j--;
                }
                //找到第一个小于基准值的data
                if( i < j ){
                    src[i] = src[j];
                    i++;
                }
                while(i < j && src[i] < orgin) {
                    i++;
                }
                //找到第一个大于基准值data
                if(i < j ){
                    src[j] = src[i];
                    j--;
                }
            }
            src[i] = orgin;
            quickSortExt(src,begin,i-1);
            quickSortExt(src,i+1,end);
        }
    }






}
